import java.util.*;
public class Leetcode {
}

//leetcode:417:太平洋大西洋水流问题
//遇难则反
//将思路为那些山峰可以即流到太平洋又能流到大西洋
//我们可以从太平洋和大西洋的外围开始找，能流到太平样或大西洋的山峰，找完之后，如果有重复的山峰，这些重复的山峰就是即流到太平洋又能流到大西洋的
class Solution1 {
    int m,n;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        boolean[][] pac = new boolean[m][n];
        boolean[][] atl = new boolean[m][n];
        for(int j = 0;j < n;j++) dfs(heights,0,j,pac);
        for(int i = 1;i < m;i++) dfs(heights,i,0,pac);

        for(int i = 0;i < m;i++) dfs(heights,i,n-1,atl);
        for(int j = 0;j < n-1;j++) dfs(heights,m-1,j,atl);

        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(pac[i][j] && atl[i][j]){
                    List<Integer> path = new ArrayList<>();
                    path.add(i);
                    path.add(j);
                    ret.add(path);
                }
            }
        }
        return ret;
    }

    public void dfs(int[][] heights,int i,int j,boolean[][] visits){
        visits[i][j] = true;
        for(int k = 0; k < 4;k++){
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && heights[x][y] >= heights[i][j]){
                dfs(heights,x,y,visits);
            }
        }
    }
}

//leetcode:529:扫雷游戏
class Solution2 {
    int m,n;
    int[] dx = {0,0,1,-1,1,-1,1,-1};
    int[] dy = {1,-1,0,0,1,-1,-1,1};
    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;
        int x = click[0], y = click[1];
        // 并且如果我们在点击的时候点到了雷就将这个雷修改为'X'，然后返回
        if(board[x][y] == 'M'){
            board[x][y] = 'X';
        }else{//如果不为雷，我们就要去找。
            dfs(board,x,y);
        }
        return board;
    }

    public void dfs(char[][] board,int i,int j){
        //此时如果这个格子周围有雷，我们需要得到周围雷的个数
        int count = 0;
        for(int k = 0; k < 8;k++){
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M' ){
                count++;
            }
        }
       //如果我们这个格子周围有雷，那么我们此时雷的个数就一定大于0，同时我们就可以将这个格子附上我们雷的个数
        if(count > 0){
            board[i][j] = (char)(count + '0');
        }else{//如果此时周围还是没有雷，我们将这个地方修改为'B'，然后继续从他的周围8个位置开始找
            board[i][j] = 'B';
            for(int k = 0; k < 8;k++){
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E' ){
                    dfs(board,x,y);
                }
            }
        }
    }
}

//leetcode:LCR:衣橱整理
//不断的伤心左右进行整理
class Solution {
    int m,n,cnt;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] visits;
    int ret = 0;
    public int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m;
        n = _n;
        cnt = _cnt;
        visits = new boolean[m][n];
        //从[0,0]开始整理
        return dfs(0,0);
    }

    //整理一个格子就让个数加1
    public int dfs(int i,int j){
        ret++;
        //标记这个位置防止重复整理
        visits[i][j] = true;
        for(int k = 0; k < 4;k++){
            int x = i + dx[k], y = j + dy[k];
            //如果还在衣橱范围里，并且是没有被整理过的位置，同时这个位置的的坐标，的各个位加起来小于等于cnt,就代表这个位置能整理
            if( x >= 0 && x < m && y >= 0 && y < n && check(x,y) && !visits[x][y]){
                dfs(x,y);
            }
        }
        //返回整理的个数
        return ret;
    }

    //进行这个坐标的各个位数相加，进行判断
    public boolean check(int i,int j){
        int tmp = 0;
        while(i != 0){
            tmp += i %10;
            i /= 10;
        }

        while(j != 0){
            tmp += j % 10;
            j /= 10;
        }

        return tmp <= cnt;
    }
}